The present invention relates to the field of instruction controlled digital computers and specifically to methods and apparatus associated with virtual and real addressing in data processing systems.
It is common in data processing systems to have a memory hierarchy wherein buffer memories of relatively low capacity, but of relatively high speed, operate in cooperation with main memories of relatively high capacity but of relatively low speed. It is desired that the vast majority of accesses, either to fetch or store information, be from the buffer memory so that the overall access time of the system is enhanced. In order to have the vast majority of accesses come from the relatively fast buffer memory, information is exchanged between the main memory and the buffer memory in accordance with predetermined algorithms.
The efficiency with which a buffer memory works in decreasing the access time of the overall system is dependent on a number of variables. For example, the variables include the capacity of the buffer memory, the capacity of the main store, the data transfer rate between stores, the replacement algorithms which determine when transfers between the main store and buffer are made, and the virtual-to-real address translation methods and apparatus.
Recent data processing systems have been designed with virtual storage in which different user programs are operable in the system. The programs identify storage locations with virtual addresses. The virtual addresses are translated dynamically to system addresses during the processing of instructions. Dynamic address translation is particularly important in multi-programming environments since different programs are free to use the same virtual addresses. To avoid interference, the system must translate virtual addresses, which are not unique, to system addresses which are unique for each executing program.
Each virtual address space typically has a virtual address space descriptor which identifies the transform tables which are to be utilized in tranforming the virtual address to a system address.
The transformation process for transforming logical addresses to system addresses is time consuming process, particularly for virtual addresses which typically have translation tables stored in main store.
In order to speed up the translation process, translation lookaside buffers have been employed. In such translation buffers, the translation information resulting from a translation of a logical address to a system address are saved once the translation has been made. When an access to the same location is desired and the translation information is already stored in the translation buffer, time is saved since the re-translation from the logical address to the system address is not required to be made.
When a translation has been made for a virtual address, the translation information is stored in the translation buffer. Thereafter when the same translation information is required, it is accessed directly from the translation buffer.
In a virtual address system for example as described in the cross-referenced applications including a translation buffer, an eviction process is carried out to delete data from the data buffer whenever translation information associated with the data is deleted from the translation buffer. The eviction process provides unwanted overhead.
Also, when a new page or other block of data is to be fetched from main store and stored into the data buffer, the process of fetching the data from main store and storing the data into the buffer is time-consuming and also is to be avoided if possible. The general processes of eviction and of fetching and storing new data into the data buffer are described in the above-identified cross-referenced applications. The overhead penalties resulting from the use of a translation buffer can be significant.
When the translation information for one virtual address replaces the translation information for another virtual address in the translation buffer, the unwanted overhead penalties, including those described above, occur.
In many operating systems a significant portion of the virtual address space is common to one or more other virtual address spaces. That is, the same system address may be specified by two or more different virtual addresses. The result is each of these different virtual addresses specify the same data locations, but because different virtual addresses or different virtual address space descriptors are employed to identify the data, the overhead penalties occur. It is desirable to avoid these overhead penalties when possible.
Accordingly, there is a need for improved memory apparatus which reduces the overhead associated with different virtual addresses which transform to the same system address.
In view of the above background, there is a need for new and improved mechanisms which are particularly useful in systems using virtual addressing.